﻿using System;
using System.Collections.Generic;
using DotNetCommon.Accessors;
using System.Collections;
using System.Collections.Concurrent;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using System.Collections.ObjectModel;
using System.Threading.Tasks;

namespace DotNetCommon.Extensions;

/// <summary>
/// <see cref="IEnumerable{T}"/>扩展类，树形结构操作
/// </summary>
public static class TreeExtensions
{
    #region Remove
    /// <summary>
    /// 从集合中删除元素
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="collection"></param>
    /// <param name="predicate"></param>
    /// <returns>返回自身</returns>
    public static ICollection<T> Remove<T>(this ICollection<T> collection, Func<T, bool> predicate)
    {
        if (collection == null) return collection;
        collection.Where(predicate).ToList().ForEach(t => collection.Remove(t));
        return collection;
    }
    #endregion

    #region FetchToTree 
    /// <summary>
    /// 从扁平的集合数据中提取树状结构（原集合数据不变), 示例:
    /// <code>
    /// var json ="""
    /// [ 
    ///   {"Id": 1,"Name": "中国","PId": null,"Children": []},
    ///   {"Id": 2,"Name": "河南","PId": 1,"Children": []},
    ///   {"Id": 3,"Name": "郑州","PId": 2,"Children": []},
    ///   {"Id": 4,"Name": "中原区","PId": 3,"Children": []},
    ///   {"Id": 5,"Name": "金水区","PId": 3,"Children": []},
    ///   {"Id": 6,"Name": "洛阳","PId": 2,"Children": []},
    /// ]
    /// """;
    /// var list = json.ToObject&lt;IEnumerable&lt;Model>>();
    /// var tree = list.FetchToTree(i => i.Id, i => i.PId, i => i.Children, i => i.PId == null || i.PId == 0);
    /// //得到的tree
    /// 
    ///         中国     
    ///          |
    ///         河南
    ///         /  \ 
    ///      郑州  洛阳
    ///      / \
    /// 中原区  金水区  
    /// </code>
    /// </summary>
    public static List<T> FetchToTree<T, TId>(this IEnumerable<T> collection,
       Func<T, TId> idSelector,
       Func<T, TId> parentIdSelector,
       Expression<Func<T, ICollection<T>>> childrenSelectorExpression,
       Func<T, bool> isRoot = null) where T : class
    {
        if (childrenSelectorExpression.Body is not MemberExpression member)
            throw new Exception($"参数{nameof(childrenSelectorExpression)}必须是一个MemberExpression，如: t=>t.Children");
        var prop = typeof(T).GetProperty(member.Member.Name);
        return _fetchToTree(collection, idSelector, parentIdSelector, isRoot, prop).ToList();
    }

    /// <summary>
    /// 从扁平的集合数据中提取树状结构（原集合数据不变), 示例:
    /// <code>
    /// var json ="""
    /// [ 
    ///   {"Id": 1,"Name": "中国","PId": null,"Children": []},
    ///   {"Id": 2,"Name": "河南","PId": 1,"Children": []},
    ///   {"Id": 3,"Name": "郑州","PId": 2,"Children": []},
    ///   {"Id": 4,"Name": "中原区","PId": 3,"Children": []},
    ///   {"Id": 5,"Name": "金水区","PId": 3,"Children": []},
    ///   {"Id": 6,"Name": "洛阳","PId": 2,"Children": []},
    /// ]
    /// """;
    /// var list = json.ToObject&lt;IEnumerable&lt;Model>>();
    /// var tree = list.FetchToTree("Id", "PId", "Children", EqualityComparer&lt;int>.Default, i => i.PId == null || i.PId == 0);
    /// //得到的tree
    /// 
    ///         中国     
    ///          |
    ///         河南
    ///         /  \ 
    ///      郑州  洛阳
    ///      / \
    /// 中原区  金水区  
    /// </code>
    /// </summary>
    public static List<T> FetchToTree<T>(this IEnumerable<T> collection,
       string idPropName,
       string parentIdPropName,
       string childrenPropName,
       IEqualityComparer compare = null,
       Func<T, bool> isRoot = null) where T : class
    {
        var props = typeof(T).GetProperties(BindingFlags.Public | BindingFlags.Instance);
        var prop = props.Where(i => i.Name == childrenPropName).FirstOrDefault().IfNullUse(props.Where(i => string.Equals(i.Name, childrenPropName, StringComparison.OrdinalIgnoreCase)).FirstOrDefault());
        AssertUtil.BeFalse(prop == null, $"class: {typeof(T).GetClassFullName()} 中不存在参数 {nameof(childrenPropName)} 指定的属性名称!");

        var accessor = Accessor.Build<T>(true);
        var parentIdType = props.FirstOrDefault(i => i.Name == parentIdPropName) ?? props.FirstOrDefault(i => string.Equals(i.Name, parentIdPropName));
        AssertUtil.BeFalse(parentIdType == null, $"class: {typeof(T).GetClassFullName()} 中不存在参数 {nameof(parentIdPropName)} 指定的属性名称!");

        compare ??= parentIdType.PropertyType.GetDefaultEqualityComparer();
        return _fetchToTree(collection, obj => accessor[obj, idPropName], obj => accessor[obj, parentIdPropName], isRoot, prop, compare).ToList();
    }

    private static readonly ConcurrentDictionary<Type, object> _cacheCompare = [];
    private static ICollection<T> _fetchToTree<T, TId>(this IEnumerable<T> collection,
       Func<T, TId> idSelector,
       Func<T, TId> parentIdSelector,
       Func<T, bool> isRoot,
       PropertyInfo prop,
       IEqualityComparer compare = null) where T : class
    {
        compare ??= _cacheCompare.GetOrAdd(typeof(TId), _ => EqualityComparer<TId>.Default) as EqualityComparer<TId>;
        var accessor = Accessor.Build<T>();
        var childrenName = prop.Name;
        var roots = new List<T>(8);
        var list = new List<T>(collection.Count());
        if (isRoot == null)
        {
            //没有筛选父节点的逻辑, 则任意节点都可能作为父节点
            /* 算法:
             * 一开始有 totalList: 这是所有的平铺数据
             * 
             * 初始遍历, 两两比较, 发现父子关系后将儿子移动父亲的容器里, 并且在新生儿列表(叫它"新生儿列表A"吧)中记录一下;
             * 为什么要有"新生儿列表A", 因为将儿子移动到父亲容器后, 它就失去做为父亲的机会, 所以还要接着给这些新生儿找儿子;
             * 
             * 接下来就是递归的东西了:
             *      在 totalList 中为 "新生儿列表A" 找儿子, 找到后将儿子移动的父亲的容器中, 并记录在新的新生儿列表中(叫它"新生儿列表B"吧);
             *      给"新生儿列表A"找完儿子后, 再去看 "新生儿列表B" 是否有元素, 有的话,继续为 "新生儿列表B" 找儿子, 找到后产生 "新生儿列表C", 依次类推, 直到不再产生新的新生儿列表为止
             */

            //初始遍历
            var totalList = collection.ToList();
            var newChilren = new List<T>();
            for (int i = 0; i < totalList.Count - 1; i++)
            {
                for (int j = i + 1; j < totalList.Count; j++)
                {
                    if (compare.Equals(parentIdSelector(totalList[j]), idSelector(totalList[i])))
                    {
                        var children = accessor[totalList[i], childrenName] as ICollection<T>;
                        if (children == null) accessor[totalList[i], childrenName] = children = new List<T>();
                        children.Add(totalList[j]);
                        newChilren.Add(totalList[j]);
                        totalList.RemoveAt(j);
                        j--;
                        continue;
                    }
                    else if (compare.Equals(parentIdSelector(totalList[i]), idSelector(totalList[j])))
                    {
                        var children = accessor[totalList[j], childrenName] as ICollection<T>;
                        if (children == null) accessor[totalList[j], childrenName] = children = new List<T>();
                        children.Add(totalList[i]);
                        newChilren.Add(totalList[i]);
                        totalList.RemoveAt(i);
                        i--;
                        break;
                    }
                }
            }
            // 递归：
            // newChildren2: 循环中产生的 "新生儿列表B、新生儿列表C等",知道不产生为止
            var newChildren2 = newChilren;
            while (newChildren2.Count > 0)
            {
                var newChildren3 = new List<T>();
                for (int i = 0; i < newChildren2.Count; i++)
                {
                    for (int j = 0; j < totalList.Count; j++)
                    {
                        if (compare.Equals(parentIdSelector(totalList[j]), idSelector(newChildren2[i])))
                        {
                            var children = accessor[newChildren2[i], childrenName] as ICollection<T>;
                            if (children == null) accessor[newChildren2[i], childrenName] = children = new List<T>();
                            children.Add(totalList[j]);
                            newChildren3.Add(totalList[j]);
                            totalList.RemoveAt(j);
                            j--;
                        }
                    }
                }
                newChildren2 = newChildren3;
            }

            return totalList;
        }
        //有根节点的选取逻辑, 先提取父节点
        foreach (var item in collection)
        {
            if (isRoot(item)) roots.Add(item);
            else list.Add(item);
        }
        FetchChildren(roots, list, idSelector, parentIdSelector);
        return roots;
        void FetchChildren(List<T> parents, List<T> collection,
            Func<T, TId> idSelector,
            Func<T, TId> parentIdSelector)
        {
            //新的父级节点
            var newParents = new List<T>();
            for (var i = 0; i < collection.Count; i++)
            {
                var item = collection[i];
                foreach (var parent in parents)
                {
                    var children = accessor[parent, childrenName] as ICollection<T>;
                    if (children == null) accessor[parent, childrenName] = children = new List<T>();
                    if (compare.Equals(parentIdSelector(item), idSelector(parent)))
                    {
                        children.Add(item);
                        newParents.Add(item);
                        collection.RemoveAt(i);
                        i--;
                        break;
                    }
                }
            }
            //产生了新的父级 再递归调用
            if (newParents.Count > 0) FetchChildren(newParents, collection, idSelector, parentIdSelector);
        }
    }
    #endregion

    #region ToFlat
    /// <summary>
    /// 将任意多级的树形列表展开(返回新的平铺集合，当treeToFlatAction参数为SetEmpty时原集合的Children属性被重置)
    /// </summary>
    /// <param name="srcArr">原属树形表</param>
    /// <param name="childrenSelectorExpression">获取子节点集合</param>
    /// <param name="treeToFlatAction">转为平铺数据后,针对原集合元素的Children属性的设置,默认为none,即:不设置</param>
    /// <returns></returns>
    public static List<T> ToFlat<T>(this IEnumerable<T> srcArr, Expression<Func<T, IEnumerable<T>>> childrenSelectorExpression, TreeToFlatAction treeToFlatAction = TreeToFlatAction.None)
    {
        if (childrenSelectorExpression.Body is not MemberExpression member)
            throw new Exception($"参数{nameof(childrenSelectorExpression)}必须是一个MemberExpression，如: t=>t.Children");
        var prop = typeof(T).GetProperty(member.Member.Name);
        var getChildren = childrenSelectorExpression.Compile();

        var res = _ToFlat(srcArr);
        if (treeToFlatAction == TreeToFlatAction.SetEmpty)
        {
            res.ForEach(i =>
            {
                var children = getChildren(i);
                //如果为null则不作更改
                if (children == null) return;
                //如果为ICollection,直接清空
                if (children is ICollection<T> collection)
                {
                    collection.Clear();
                }
                else if (prop.CanWrite && children is IEnumerable<T>)
                {
                    prop.SetValue(i, Array.Empty<T>());
                }
            });
        }
        else if (treeToFlatAction == TreeToFlatAction.SetNull)
        {
            if (prop.CanWrite)
            {
                res.ForEach(i =>
                {
                    if (getChildren(i) != null)
                    {
                        prop.SetValue(i, null);
                    }
                });
            }
        }
        else if (treeToFlatAction == TreeToFlatAction.SetEmptyCollection)
        {
            if (prop.CanWrite)
            {
                res.ForEach(i =>
                {
                    var children = getChildren(i);
                    if (children == null)
                    {
                        prop.SetValue(i, new List<T>());
                    }
                    else
                    {
                        //如果为ICollection,直接清空
                        if (children is ICollection<T> collection)
                        {
                            collection.Clear();
                        }
                        else if (prop.CanWrite && children is IEnumerable<T>)
                        {
                            //如果为数组或IEnumerable则设为空数组
                            prop.SetValue(i, Array.Empty<T>());
                        }
                    }
                });
            }
        }
        return res;

        List<T> _ToFlat(IEnumerable<T> srcArr)
        {
            var res = new List<T>();
            if (srcArr != null && srcArr.Any())
            {
                srcArr.ForEach(i =>
                {
                    res.Add(i);
                    var children = getChildren(i);
                    if (children != null && children.Any())
                    {
                        var list = _ToFlat(children);
                        if (list != null && list.Count > 0) res.AddRange(list);
                    }
                });
            }
            return res;
        }
    }
    #endregion

    #region FilterTree
    /// <summary>
    /// 过滤树结构(注意原始集合已改变)
    /// </summary>
    private static void FilterTree<T>(this IList<T> tree, Func<T, IList<T>> childrenSelector, Predicate<T> filterExpression, bool withAllChildren, List<T> tmpList)
    {
        //倒序遍历,方便移除
        for (var i = tree.Count - 1; i >= 0; i--)
        {
            var child = tree[i];
            var showme = false;
            if (filterExpression(child))
            {
                showme = true;
                tmpList?.Add(child);
            }
            //当前节点已命中且指定返回所有子节点,可以直接返回了
            if (withAllChildren && showme) continue;
            var showchild = false;
            var children = childrenSelector(child);
            if (children != null && children.Count > 0)
            {
                FilterTree(children, childrenSelector, filterExpression, withAllChildren, showme ? null : tmpList);
                if (children.Count > 0)
                {
                    showchild = true;
                }
            }
            if (showme == false && showchild == false)
            {
                //自身和字节点均没有被命中，则移除自身
                tree.RemoveAt(i);
            }
        }
    }

    /// <summary>
    /// 过滤树结构(注意原始集合已改变)
    /// </summary>
    private static async Task FilterTree<T>(this IList<T> tree, Func<T, IList<T>> childrenSelector, Func<T, Task<bool>> filterExpression, bool withAllChildren, List<T> tmpList)
    {
        //倒序遍历,方便移除
        for (var i = tree.Count - 1; i >= 0; i--)
        {
            var child = tree[i];
            var showme = false;
            if (await filterExpression(child))
            {
                showme = true;
                tmpList?.Add(child);
            }
            //当前节点已命中且指定返回所有子节点,可以直接返回了
            if (withAllChildren && showme) continue;
            var showchild = false;
            var children = childrenSelector(child);
            if (children != null && children.Count > 0)
            {
                await FilterTree(children, childrenSelector, filterExpression, withAllChildren, showme ? null : tmpList);
                if (children.Count > 0)
                {
                    showchild = true;
                }
            }
            if (showme == false && showchild == false)
            {
                //自身和字节点均没有被命中，则移除自身
                tree.RemoveAt(i);
            }
        }
    }

    /// <summary>
    /// 过滤树结构(注意原始集合已改变), 返回自身 <br />
    /// 示例:
    /// <code>
    /// 
    ///         中国      list.FilterTree(
    ///          |           childrenSelector: i => i.Children,
    ///         河南         filterExpression: i => i.Name == "郑州",     => 
    ///         /  \         withAllChildren: true,
    ///      郑州  洛阳       withAllParents: false)                               郑州
    ///      / \                                                                  / \
    /// 中原区  金水区                                                        中原区  金水区
    /// 
    /// 
    /// 
    /// 
    ///                   list.FilterTree(                                             中国   
    ///                      childrenSelector: i => i.Children,                         |     
    ///                      filterExpression: i => i.Name == "郑州",     =>           河南   
    ///                      withAllChildren: false,                                    |    
    ///                      withAllParents: true)                                     郑州
    ///                      
    /// </code>
    /// </summary>
    public static IList<T> FilterTree<T>(this IList<T> tree, Func<T, IList<T>> childrenSelector, Predicate<T> filterExpression, bool withAllChildren = false, bool withAllParents = true)
    {
        List<T> tmpList = null;
        if (!withAllParents)
        {
            //不输出父节点,则收集分支上首个命中的节点
            tmpList = [];
        }
        FilterTree(tree, childrenSelector, filterExpression, withAllChildren, tmpList);
        if (withAllParents) return tree;
        else
        {
            tree.Clear();
            tree.AddRange(tmpList);
            return tree;
        }
    }

    public static async Task<IList<T>> FilterTree<T>(this IList<T> tree, Func<T, IList<T>> childrenSelector, Func<T, Task<bool>> filterExpression, bool withAllChildren = false, bool withAllParents = true)
    {
        List<T> tmpList = null;
        if (!withAllParents)
        {
            //不输出父节点,则收集分支上首个命中的节点
            tmpList = [];
        }
        await FilterTree(tree, childrenSelector, filterExpression, withAllChildren, tmpList);
        if (withAllParents) return tree;
        else
        {
            tree.Clear();
            tree.AddRange(tmpList);
            return tree;
        }
    }

    /// <inheritdoc cref="FilterTree{T}(IList{T}, Func{T, IList{T}}, Predicate{T}, bool, bool)"/>
    public static List<T> FilterTree<T>(this List<T> tree, Func<T, IList<T>> childrenSelector, Predicate<T> filterExpression, bool withAllChildren = false, bool withAllParents = true)
    {
        List<T> tmpList = null;
        if (!withAllParents)
        {
            //不输出父节点,则收集分支上首个命中的节点
            tmpList = [];
        }
        FilterTree(tree, childrenSelector, filterExpression, withAllChildren, tmpList);
        if (withAllParents) return tree;
        else
        {
            tree.Clear();
            tree.AddRange(tmpList);
            return tree;
        }
    }

    /// <inheritdoc cref="FilterTree{T}(IList{T}, Func{T, IList{T}}, Predicate{T}, bool, bool)"/>
    public static async Task<List<T>> FilterTree<T>(this List<T> tree, Func<T, IList<T>> childrenSelector, Func<T, Task<bool>> filterExpression, bool withAllChildren = false, bool withAllParents = true)
    {
        List<T> tmpList = null;
        if (!withAllParents)
        {
            //不输出父节点,则收集分支上首个命中的节点
            tmpList = [];
        }
        await FilterTree(tree, childrenSelector, filterExpression, withAllChildren, tmpList);
        if (withAllParents) return tree;
        else
        {
            tree.Clear();
            tree.AddRange(tmpList);
            return tree;
        }
    }
    #endregion

    #region VisitTree
    /// <summary>
    /// 深度优先(DFS), 前序遍历.<br />
    /// 示例, 下面的森林遍历顺序已在括号中
    /// <code>
    ///        中国(1)            美国(6)
    ///       /    \             /     \
    ///    河南(2)  湖北(5)  华盛顿州(7) 得克萨斯州(8)
    ///    /   \ 
    /// 郑州(3) 洛阳(4)
    /// </code>
    /// </summary>
    public static IEnumerable<T> VisitTree<T>(this IEnumerable<T> tree, Func<T, IEnumerable<T>> childrenSelector, Action<VisitTreeContext<T>> action)
    {
        if (tree == null || action == null) return tree;
        AssertUtil.NotNull(childrenSelector);
        foreach (var node in tree)
        {
            var children = childrenSelector(node);
            var isLeaf = children == null || !children.Any();
            var ctx = new VisitTreeContext<T>()
            {
                Current = node,
                IsLeaf = isLeaf,
                Parent = null
            };
            _recurseTree(ctx);
            if (ctx.BreakRquested) break;
        }
        return tree;

        void _recurseTree(VisitTreeContext<T> ctx)
        {
            //先执行用户逻辑
            action(ctx);
            //检测用户行为
            //是否请求中断遍历
            if (ctx.BreakRquested)
            {
                //遍历完当前节点的后续逻辑
                ctx.RunAfterAct?.Invoke();
                //向上传导
                if (ctx.Parent != null) ctx.Parent.BreakRquested = true;
                return;
            }
            //是否请求继续下个兄弟节点遍历, 而不是继续下探
            if (ctx.NextSiblingRquested)
            {
                //遍历完当前节点的后续逻辑
                ctx.RunAfterAct?.Invoke();
                return;
            }
            if (!ctx.IsLeaf)
            {
                //遍历子节点
                //先把自身加入上下文
                ctx.InternalParents.Add(ctx.Current);
                var children = childrenSelector(ctx.Current);
                foreach (var n in children)
                {
                    //深度+1
                    ctx.InternalConter.Deep++;
                    var childrenNew = childrenSelector(n);
                    var isLeafNew = childrenNew == null || !childrenNew.Any();
                    var newCtx = new VisitTreeContext<T>
                    {
                        Current = n,
                        IsLeaf = isLeafNew,
                        Parent = ctx
                    };
                    //递归调用
                    _recurseTree(newCtx);
                    //深度-1
                    ctx.InternalConter.Deep--;
                    if (newCtx.BreakRquested)
                    {
                        if (newCtx.Parent != null) newCtx.Parent.BreakRquested = true;
                        return;
                    }
                }
                //把自身从上下文中移除
                var index = ctx.InternalParents.LastIndexOf(ctx.Current);
                ctx.InternalParents.RemoveAt(index);
            }
            //遍历完当前节点(及其子孙节点)的后续逻辑
            ctx.RunAfterAct?.Invoke();
        }
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<IEnumerable<T>> VisitTree<T>(this IEnumerable<T> tree, Func<T, IEnumerable<T>> childrenSelector, Func<VisitTreeContext<T>, Task> action)
    {
        if (tree == null || action == null) return tree;
        AssertUtil.NotNull(childrenSelector);
        foreach (var node in tree)
        {
            var children = childrenSelector(node);
            var isLeaf = children == null || !children.Any();
            var ctx = new VisitTreeContext<T>()
            {
                Current = node,
                IsLeaf = isLeaf,
                Parent = null
            };
            await _recurseTree(ctx);
            if (ctx.BreakRquested) break;
        }
        return tree;

        async Task _recurseTree(VisitTreeContext<T> ctx)
        {
            //先执行用户逻辑
            await action(ctx);
            //检测用户行为
            //是否请求中断遍历
            if (ctx.BreakRquested)
            {
                //遍历完当前节点的后续逻辑
                ctx.RunAfterAct?.Invoke();
                //向上传导
                if (ctx.Parent != null) ctx.Parent.BreakRquested = true;
                return;
            }
            //是否请求继续下个兄弟节点遍历, 而不是继续下探
            if (ctx.NextSiblingRquested)
            {
                //遍历完当前节点的后续逻辑
                ctx.RunAfterAct?.Invoke();
                return;
            }
            if (!ctx.IsLeaf)
            {
                //遍历子节点
                //先把自身加入上下文
                ctx.InternalParents.Add(ctx.Current);
                var children = childrenSelector(ctx.Current);
                foreach (var n in children)
                {
                    //深度+1
                    ctx.InternalConter.Deep++;
                    var childrenNew = childrenSelector(n);
                    var isLeafNew = childrenNew == null || !childrenNew.Any();
                    var newCtx = new VisitTreeContext<T>
                    {
                        Current = n,
                        IsLeaf = isLeafNew,
                        Parent = ctx
                    };
                    //递归调用
                    await _recurseTree(newCtx);
                    //深度-1
                    ctx.InternalConter.Deep--;
                    if (newCtx.BreakRquested)
                    {
                        if (newCtx.Parent != null) newCtx.Parent.BreakRquested = true;
                        return;
                    }
                }
                //把自身从上下文中移除
                var index = ctx.InternalParents.LastIndexOf(ctx.Current);
                ctx.InternalParents.RemoveAt(index);
            }
            //遍历完当前节点(及其子孙节点)的后续逻辑
            ctx.RunAfterAct?.Invoke();
        }
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static ICollection<T> VisitTree<T>(this ICollection<T> tree, Func<T, IEnumerable<T>> childrenSelector, Action<VisitTreeContext<T>> action)
    {
        return VisitTree(tree as IEnumerable<T>, childrenSelector, action) as ICollection<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<ICollection<T>> VisitTree<T>(this ICollection<T> tree, Func<T, IEnumerable<T>> childrenSelector, Func<VisitTreeContext<T>, Task> action)
    {
        return await VisitTree(tree as IEnumerable<T>, childrenSelector, action) as ICollection<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static IList<T> VisitTree<T>(this IList<T> tree, Func<T, IEnumerable<T>> childrenSelector, Action<VisitTreeContext<T>> action)
    {
        return VisitTree(tree as IEnumerable<T>, childrenSelector, action) as IList<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<IList<T>> VisitTree<T>(this IList<T> tree, Func<T, IEnumerable<T>> childrenSelector, Func<VisitTreeContext<T>, Task> action)
    {
        return await VisitTree(tree as IEnumerable<T>, childrenSelector, action) as IList<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static IReadOnlyCollection<T> VisitTree<T>(this IReadOnlyCollection<T> tree, Func<T, IEnumerable<T>> childrenSelector, Action<VisitTreeContext<T>> action)
    {
        return VisitTree(tree as IEnumerable<T>, childrenSelector, action) as IReadOnlyCollection<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<IReadOnlyCollection<T>> VisitTree<T>(this IReadOnlyCollection<T> tree, Func<T, IEnumerable<T>> childrenSelector, Func<VisitTreeContext<T>, Task> action)
    {
        return await VisitTree(tree as IEnumerable<T>, childrenSelector, action) as IReadOnlyCollection<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static IReadOnlyList<T> VisitTree<T>(this IReadOnlyList<T> tree, Func<T, IEnumerable<T>> childrenSelector, Action<VisitTreeContext<T>> action)
    {
        return VisitTree(tree as IEnumerable<T>, childrenSelector, action) as IReadOnlyList<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<IReadOnlyList<T>> VisitTree<T>(this IReadOnlyList<T> tree, Func<T, IEnumerable<T>> childrenSelector, Func<VisitTreeContext<T>, Task> action)
    {
        return await VisitTree(tree as IEnumerable<T>, childrenSelector, action) as IReadOnlyList<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static List<T> VisitTree<T>(this List<T> tree, Func<T, IEnumerable<T>> childrenSelector, Action<VisitTreeContext<T>> action)
    {
        return VisitTree(tree as IEnumerable<T>, childrenSelector, action) as List<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<List<T>> VisitTree<T>(this List<T> tree, Func<T, IEnumerable<T>> childrenSelector, Func<VisitTreeContext<T>, Task> action)
    {
        return await VisitTree(tree as IEnumerable<T>, childrenSelector, action) as List<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static ReadOnlyCollection<T> VisitTree<T>(this ReadOnlyCollection<T> tree, Func<T, IEnumerable<T>> childrenSelector, Action<VisitTreeContext<T>> action)
    {
        return VisitTree(tree as IEnumerable<T>, childrenSelector, action) as ReadOnlyCollection<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<ReadOnlyCollection<T>> VisitTree<T>(this ReadOnlyCollection<T> tree, Func<T, IEnumerable<T>> childrenSelector, Func<VisitTreeContext<T>, Task> action)
    {
        return await VisitTree(tree as IEnumerable<T>, childrenSelector, action) as ReadOnlyCollection<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static T[] VisitTree<T>(this T[] tree, Func<T, IEnumerable<T>> childrenSelector, Action<VisitTreeContext<T>> action)
    {
        return VisitTree(tree as IEnumerable<T>, childrenSelector, action) as T[];
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<T[]> VisitTree<T>(this T[] tree, Func<T, IEnumerable<T>> childrenSelector, Func<VisitTreeContext<T>, Task> action)
    {
        return await VisitTree(tree as IEnumerable<T>, childrenSelector, action) as T[];
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static IEnumerable<T> VisitTree<T>(this IEnumerable<T> tree, string childrenPropName, Action<VisitTreeContext<T>> action) where T : class
    {
        AssertUtil.NotNull(childrenPropName);
        var accessor = Accessor.Build<T>(true, false);
        return VisitTree(tree, t => accessor[t, childrenPropName] as IEnumerable<T>, action);
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<IEnumerable<T>> VisitTree<T>(this IEnumerable<T> tree, string childrenPropName, Func<VisitTreeContext<T>, Task> action) where T : class
    {
        AssertUtil.NotNull(childrenPropName);
        var accessor = Accessor.Build<T>(true, false);
        return await VisitTree(tree, t => accessor[t, childrenPropName] as IEnumerable<T>, action);
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static List<T> VisitTree<T>(this List<T> tree, string childrenPropName, Action<VisitTreeContext<T>> action) where T : class
    {
        AssertUtil.NotNull(childrenPropName);
        var accessor = Accessor.Build<T>(true, false);
        return VisitTree(tree as IEnumerable<T>, t => accessor[t, childrenPropName] as IEnumerable<T>, action) as List<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<List<T>> VisitTree<T>(this List<T> tree, string childrenPropName, Func<VisitTreeContext<T>, Task> action) where T : class
    {
        AssertUtil.NotNull(childrenPropName);
        var accessor = Accessor.Build<T>(true, false);
        return await VisitTree(tree as IEnumerable<T>, t => accessor[t, childrenPropName] as IEnumerable<T>, action) as List<T>;
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static T[] VisitTree<T>(this T[] tree, string childrenPropName, Action<VisitTreeContext<T>> action) where T : class
    {
        AssertUtil.NotNull(childrenPropName);
        var accessor = Accessor.Build<T>(true, false);
        return VisitTree(tree as IEnumerable<T>, t => accessor[t, childrenPropName] as IEnumerable<T>, action) as T[];
    }

    /// <inheritdoc cref="TreeExtensions.VisitTree{T}(IEnumerable{T}, Func{T, IEnumerable{T}}, Action{VisitTreeContext{T}})" />
    public static async Task<T[]> VisitTree<T>(this T[] tree, string childrenPropName, Func<VisitTreeContext<T>, Task> action) where T : class
    {
        AssertUtil.NotNull(childrenPropName);
        var accessor = Accessor.Build<T>(true, false);
        return await VisitTree(tree as IEnumerable<T>, t => accessor[t, childrenPropName] as IEnumerable<T>, action) as T[];
    }
    #endregion
}

/// <summary>
/// ICollection.ToFlat()方法的参数
/// </summary>
public enum TreeToFlatAction
{
    /// <summary>
    /// 不对原有的Children属性做任何操作
    /// </summary>
    None,
    /// <summary>
    /// 设置为空集合(原来的Children为null则为null，否则为空集合)
    /// </summary>
    SetEmpty,
    /// <summary>
    /// 设置为空集合(将原来的Children设为null)
    /// </summary>
    SetNull,
    /// <summary>
    /// 设置为空集合(将原来的Children设为元素个数为空的集合)
    /// </summary>
    SetEmptyCollection
}

/// <summary>
/// 树节点遍历上下文
/// </summary>
/// <typeparam name="T"></typeparam>
public class VisitTreeContext<T>
{
    /// <summary>
    /// 当前节点
    /// </summary>
    public T Current { get; internal set; }
    /// <summary>
    /// 当前节点深度,从0开始
    /// </summary>
    public int DeepIndex => InternalConter.Deep;
    /// <summary>
    /// 当前节点是否是叶子节点
    /// </summary>
    public bool IsLeaf { get; internal set; }

    /// <summary>
    /// 当前节点的父节点集合
    /// <code>
    /// 示例:
    ///        中国
    ///       /    \
    ///    河南     湖北
    ///    /  \ 
    /// 郑州  洛阳
    /// 
    /// 如果当前节点为: 郑州, 则得到: [中国, 河南]
    /// </code>
    /// </summary>
    /// <remarks>注意: 每次调用都返回一个新的集合</remarks>
    public ReadOnlyCollection<T> Parents => InternalParents.AsReadOnly();

    private List<T> _parents = null;
    /// <summary>
    /// 当前节点的父节点集合, 下面的森林在整个遍历中会产生两个容器
    /// <code>
    ///        中国               美国
    ///       /    \            /     \
    ///    河南     湖北    华盛顿州   得克萨斯州
    ///    /  \ 
    /// 郑州  洛阳
    /// </code>
    /// </summary>
    internal List<T> InternalParents
    {
        get
        {
            _parents ??= Parent?.InternalParents ?? [];
            return _parents;
        }
    }

    /// <summary>
    /// 当前节点的父节点和自身集合
    /// <code>
    /// 示例:
    ///        中国
    ///       /    \
    ///    河南     湖北
    ///    /  \ 
    /// 郑州  洛阳
    /// 
    /// 如果当前节点为: 郑州, 则得到: [中国, 河南, 郑州]
    /// </code>
    /// </summary>
    /// <remarks>注意: 每次调用都返回一个新的集合</remarks>
    public ReadOnlyCollection<T> ParentsWithSelf
    {
        get
        {
            var list = new List<T>(InternalParents.Count + 1);
            list.AddRangeFluent(InternalParents).Add(Current);
            return list.AsReadOnly();
        }
    }

    /// <summary>
    /// 请求中断遍历, 示例:
    /// <code>
    ///        中国
    ///       /    \
    ///    河南     湖北
    ///    /  \ 
    /// 郑州  洛阳
    /// 
    /// var dirs = new List&lt;string>();// 得到的郑州的目录, 运行完后应该是: ["中国", "河南"]
    /// list.VisitTree(i => i.Children, ctx =>
    /// {
    ///     if(ctx.Current.Name == "郑州") 
    ///     {
    ///         ctx.BreakRecurse();
    ///         // 注意: BreakRecurse() 只是设置了标记, 如果这里不 return 的话, 最终得到的 dirs 是: ["中国", "河南", "郑州"]
    ///         return;
    ///     }
    ///     dirs.Add(ctx.Current.Name);
    /// });
    /// </code>
    /// </summary>
    public void BreakRecurse()
    {
        BreakRquested = true;
    }

    /// <summary>
    /// 继续下个兄弟节点的遍历(跳过子节点), 示例:
    /// <code>
    ///        中国
    ///       /    \
    ///    河南     湖北
    ///    /  \ 
    /// 郑州  洛阳
    /// 
    /// var visitNodes = new List&lt;string>();// 运行完后应该是: ["中国", "湖北"]
    /// list.VisitTree(i => i.Children, ctx =>
    /// {
    ///     if(ctx.Current.Name == "河南") 
    ///     {
    ///         ctx.NextSibling();
    ///         // 注意: NextSibling() 只是设置了标记, 如果这里不 return 的话, 最终得到的 visitNodes 是: ["中国", "河南", "湖北"]
    ///         return;
    ///     }
    ///     visitNodes.Add(ctx.Current.Name);
    /// });
    /// </code>
    /// </summary>
    public void NextSibling()
    {
        NextSiblingRquested = true;
    }

    internal Action RunAfterAct { get; set; }
    /// <summary>
    /// 当完成此节点遍历后再执行的逻辑, 示例:
    /// <code>
    ///        中国
    ///       /    \
    ///    河南     湖北
    ///    /  \ 
    /// 郑州  洛阳
    /// 
    /// var visitNodes = new List&lt;string>();// 运行完后应该是: ["中国", "河南", "郑州", "洛阳", "周口", "湖北"]
    /// list.VisitTree(i => i.Children, ctx =>
    /// {
    ///     if(ctx.Current.Name == "河南")
    ///     {
    ///         ctx.RunAfter(() => visitNodes.Add("周口"));
    ///     }
    ///     visitNodes.Add(ctx.Current.Name);
    /// });
    /// </code>
    /// </summary>
    public void RunAfter(Action act)
    {
        RunAfterAct = act;
    }

    /// <summary>
    /// 是否请求中断遍历
    /// </summary>
    internal bool BreakRquested { set; get; }

    /// <summary>
    /// 是否请求继续下个兄弟节点遍历
    /// </summary>
    internal bool NextSiblingRquested { set; get; }

    /// <summary>
    /// 父节点
    /// </summary>
    internal VisitTreeContext<T> Parent { get; set; }

    private Counter _counter = null;
    /// <summary>
    /// 当前节点的深度计数, 下面的森林在整个遍历中会产生两个计数器
    /// <code>
    ///        中国               美国
    ///       /    \            /     \
    ///    河南     湖北    华盛顿州   得克萨斯州
    ///    /  \ 
    /// 郑州  洛阳
    /// </code>
    /// </summary>
    internal Counter InternalConter
    {
        get
        {
            _counter ??= Parent?.InternalConter ?? new Counter();
            return _counter;
        }
    }
}

internal class Counter
{
    public int Deep { get; set; }
}